Backtracking

Trial- and Error Verfahren; Rücksetzalgorithmus

* * *

Back|tra|cking 〈[bæ̣ktrækıŋ] n.; - od. -s; unz.; EDV〉 Programmier- bzw. Suchstrategie, die von bestimmten Problempunkten ausgehend Lösungswege entwickelt, wobei der bis dahin aktuelle (Daten-)Bestand gesichert (u. gegebenenfalls rückverfolgt) wird, falls sich der Weg als eindeutig falsch erweist [engl., „Rückverfolgung“]

* * *

Backtracking

 

[dt. »Zurückverfolgung«] das, ein Problemlöseverfahren, bei dem versucht wird, Teillösungen eines Problems systematisch zu einer Gesamtlösung auszubauen. Falls in einem gewissen Stadium ein weiterer Ausbau einer vorliegenden Teillösung nicht mehr möglich ist (Sackgasse), werden einer oder mehrere der letzten Teilschritte rückgängig gemacht. Die dann erhaltene reduzierte Teillösung versucht man auf einem anderen Weg wieder auszubauen. Das Zurücknehmen von Schritten und erneute Vorangehen wird so lange wiederholt, bis eine Lösung des Problems gefunden ist oder bis man erkennt, dass das Problem keine Lösung besitzt.

 

Ein Beispiel für das Backtracking ist die Suche in einem Labyrinth. Das Labyrinth kann als Baum dargestellt werden, bei dem der Ausgangspunkt die Wurzel und jede Verzweigungsmöglichkeit einen Knoten darstellt. Kein, ein oder mehrere Wege im Baum führen dann zum Zielpunkt. Die Suche mit Backtracking beginnt, indem von der Wurzel aus von Knoten zu Knoten ein Weg eingeschlagen wird (z.B. »immer links abzweigen«). Gelangt man in eine Sackgasse, geht man einen Knoten zurück und probiert die nächste Verzweigungsmöglichkeit aus (z. B. »an dieser Stelle rechts abzweigen«), bis diese zum Ziel oder wieder in eine Sackgasse führt. In letzterem Fall geht man wieder einen Schritt zurück und geht die nächstmögliche Verzweigung an. Erst wenn alle Verzweigungen an einem Knoten in Sackgassen führen, springt man einen weiteren Knoten zurück. Auf diese Art und Weise wird der ganze Baum durchfahren, und falls es einen Zielpunkt, eine Lösung gibt, wird diese auch gefunden.

 

Das Backtracking ist ein sehr einfaches Verfahren, das nach der Methode Versuch und Irrtum (Trial and Error) arbeitet. Es wird eingesetzt, wenn die Teillösungen keinen Aufschluss über die Gesamtlösung liefern. Backtracking kommt z. B. bei der Problemlösung mithilfe künstlicher Intelligenz (KI) zum Einsatz. Auch die Lösungssuche bei Prolog verwendet Backtracking. Ab einer bestimmten Zahl von Verzweigungsebenen wird das Verfahren impraktikabel, da die Rechenzeit exponenziell zur Ebenenzahl zunimmt.